package com.wtgroup.demo.mianshi.算法.动态规划.暴力递归;

import com.wtgroup.demo.common.judge.Judger;
import com.wtgroup.demo.common.util.Sout;
import com.wtgroup.demo.common.util.Tools;

/**
 * N个皇后放 NxN 格子，同行、同列、同斜线，只能放一个.
 * 共有几种解法?
 *
 * @author nisus
 * @version 0.1
 * @since 2023/5/9 16:50
 */
public class Q_N皇后问题 {

    public static void main(String[] args) {
        testTime2();
    }

    private static void test2() {
        D d = new D();
        Judger.ofi((i) -> {
            int N = i + 1;
            return d.func(N) == S_位.num2(N);
        }).setIterCount(13).start().print();
    }

    private static void testTime() {
        D d = new D();
        D_优化常数项_bak d2 = new D_优化常数项_bak();
        Judger.ofi((i) -> {
            long cost1 = Tools.time(() -> {
                int r1 = d.func(i);
            });
            long cost2 = Tools.time(() -> {
                int r2 = d2.func(i);
            });

            Sout.println(cost1, cost2, cost1 - cost2);
            return true;
        }).setIterCount(14).start().print();
    }

    private static void testTime2() {
        D d = new D();
        Judger.ofi((i) -> {
            int N = i + 1;
            long cost1 = Tools.time(() -> {
                int r1 = d.func(N);
            });
            long cost2 = Tools.time(() -> {
                int r2 = S_位.num2(N);
            });

            Sout.println(cost1, cost2, cost1 - cost2);
            return true;
        }).setIterCount(14).start().print();
    }

    private static void test1() {
        Judger.of(() -> {
            // System.out.println(new D().func(1));
            // System.out.println(new D().func(2));
            // System.out.println(new D().func(3));
            // System.out.println(new D().func(4));
            // System.out.println(new D().func(5));

            for (int i = 1; i <= 11; i++) {
                int r1 = new D().func(i);
                int r2 = new D_优化常数项_bak().func(i);
                if (r1 != r2) {
                    Sout.println(r1, ", ", r2);
                    throw new RuntimeException("ooooooxxx");
                }
            }
            // System.out.println(new D_优化常数项().func(4));

            return true;
        }).setIterCount(1).start().print();
    }

    static class D {

        int func(int N) {
            // mark 可以简化成一维数组, 索引下标代表行, 元素值代表列
            int[][] mark = new int[N][N];
            int r = func0(N, mark, 0);
            return r;
        }

        private int func0(int N, int[][] mark, int i) {
            if (i >= N) {
                // N-1 行能放, 收集到一种摆法
                return 1;
            }

            int res = 0;
            for (int j = 0; j < N; j++) {
                if (invalid(N, mark, i, j)) continue;

                // (i,j) 能放, 那么在此基础上, 下一行继续同样的尝试
                mark[i][j] = 1;
                int next = func0(N, mark, i + 1);
                // 一定要恢复现场
                mark[i][j] = 0;
                res += next;
            }

            return res;
        }

        private boolean invalid(int N, int[][] mark, int i, int j) {
            boolean isBiasMarked = false;
            for (int row = i - 1, d = 1; row >= 0 && !isBiasMarked; row--, d++) {
                if (isBiasMarked) {
                    break;
                }

                if (mark[row][j] > 0) {
                    return true;
                }

                if (j - d >= 0) {
                    isBiasMarked = mark[row][j - d] > 0;
                }
                if (!isBiasMarked && j + d < N) {
                    isBiasMarked = mark[row][j + d] > 0;
                }
            }
            if (isBiasMarked) {
                return true;
            }
            return false;
        }

        // private boolean columnMarked(int[][] mark, int col) {
        //     for (int i = 0; i < mark.length; i++) {
        //         if (mark[i][col] > 0) {
        //             return true;
        //         }
        //     }
        //
        //     return false;
        // }
        //
        // private boolean rowMarked(int[][] mark, int row) {
        //     for (int i = 0; i < mark[0].length; i++) {
        //         if (mark[row][i] > 0) {
        //             return true;
        //         }
        //     }
        //
        //     return false;
        // }

    }

    /**
     * 位运算
     * 我自己的思路
     * 可以说没有优化效果
     */
    static class D_优化常数项_bak {
        /*
        mark[] 记录每行, 值(二进制)含列位置
        遍历每行, 分别和三个数值 | 运算, 0001000,
        左对角线, 1 << , 1000000, 右对角线, 0001001, ...
        ~~进一步优化, mark[] 合并成一个二进制表示, 之前每行的摆放信息都有~~
         */

        int func(int N) {
            int[] mark = new int[N];
            return func0(N, mark, 0);
        }

        private int func0(int N, int[] mark, int i) {
            if (i >= N) {
                // N-1 行能放, 收集到一种摆法
                return 1;
            }

            int res = 0;
            for (int j = 0; j < N; j++) { // 右->左
                boolean isValid = isValid(mark, i, j);
                if (!isValid) {
                    continue;
                }

                // (i,j) 能放, 那么在此基础上, 下一行继续同样的尝试
                mark[i] = 1 << j;
                int next = func0(N, mark, i + 1);
                // 一定要恢复现场
                mark[i] = 0;
                res += next;
            }

            return res;
        }

        private static boolean isValid(int[] mark, int i, int j) {
            boolean isValid = true;
            int bi = 1 << j;
            for (int m = 0; m < i; m++) {
                if (isValid == false) {
                    break;
                }
                isValid = (bi & mark[m]) == 0;
                int d = i - m;
                if (isValid && j + d <= 32) {
                    isValid = ((bi << d) & mark[m]) == 0;
                }
                if (isValid && j - d >= 0) {
                    isValid = ((bi >>> d) & mark[m]) == 0;
                }
            }
            return isValid;
        }


    }

    /*
    列限制逐行 或, 每行的皇后信息都含了.
    对角线? 每次下移动一行, 左移,右移, 最后自然
     */

    static class S_位 {
        // 请不要超过32皇后问题
        public static int num2(int n) {
            if (n < 1 || n > 32) {
                return 0;
            }
            // 如果你是13皇后问题，limit 最右13个1，其他都是0
            int limit = n == 32 ? -1 : (1 << n) - 1;
            return process2(limit, 0, 0, 0);
        }

        // 7皇后问题
        // limit : 0....0 1 1 1 1 1 1 1
        // 之前皇后的列影响：colLim
        // 之前皇后的左下对角线影响：leftDiaLim
        // 之前皇后的右下对角线影响：rightDiaLim
        public static int process2(int limit, int colLim, int leftDiaLim, int rightDiaLim) {
            if (colLim == limit) {
                return 1;
            }
            // pos中所有是1的位置，是你可以去尝试皇后的位置
            int pos = limit & (~(colLim | leftDiaLim | rightDiaLim));
            int mostRightOne = 0;
            int res = 0;
            while (pos != 0) {
                mostRightOne = pos & (~pos + 1);
                pos = pos - mostRightOne;
                res += process2(limit, colLim | mostRightOne, (leftDiaLim | mostRightOne) << 1,
                        (rightDiaLim | mostRightOne) >>> 1);
            }
            return res;
        }
    }

}
